import { btPrint } from "hy-algokit";

class Node<T> {
  value: T;
  constructor(value: T) {
    this.value = value;
  }
}

export default Node;

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent: TreeNode<T> | null = null;

  //是否是左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this);
  }

  //是否是右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this);
  }
}

//二叉搜索树
export class BinarySearchTree<T> {
  protected root: TreeNode<T> | null = null;

  //递归插入
  private insertNode(root: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < root.value) {
      //左子树
      if (!root.left) {
        root.left = newNode;
        newNode.parent = root;
      } else {
        this.insertNode(root.left, newNode);
      }
    } else {
      //右子树
      if (!root.right) {
        root.right = newNode;
        newNode.parent = root;
      } else {
        this.insertNode(root.right, newNode);
      }
    }
  }

  protected createNode(value: T): TreeNode<T> {
    return new TreeNode(value);
  }

  //检查节点是否平衡
  protected checkBalancedNode(node: TreeNode<T>) {}

  //插入操作
  insert(value: T) {
    const newNode = this.createNode(value);
    if (!this.root) {
      //无根节点
      this.root = newNode;
    } else {
      //有根节点
      this.insertNode(this.root, newNode);
    }

    this.checkBalancedNode(newNode);
  }

  //打印
  print() {
    btPrint(this.root);
  }

  //先序遍历递归
  private preOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      console.log(root.value);
      this.preOrderTraverseLoop(root.left);
      this.preOrderTraverseLoop(root.right);
    }
  }
  //先序遍历
  preOrderTraverse() {
    this.preOrderTraverseLoop(this.root);
  }

  //中序遍历递归
  private inOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.inOrderTraverseLoop(root.left);
      console.log(root.value);
      this.inOrderTraverseLoop(root.right);
    }
  }
  //中序遍历
  inOrderTraverse() {
    this.inOrderTraverseLoop(this.root);
  }

  //后序遍历递归
  private postTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.postTraverseLoop(root.left);
      this.postTraverseLoop(root.right);
      console.log(root.value);
    }
  }
  //后序遍历
  postOrderTraverse() {
    this.postTraverseLoop(this.root);
  }

  //层序遍历
  levelOrderTraverse() {
    if (!this.root) return;

    //根节点入栈
    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    //根节点出栈，同时左节点和右节点入栈
    while (queue.length) {
      const node = queue.shift();
      console.log(node?.value);
      node?.left && queue.push(node?.left);
      node?.right && queue.push(node?.right);
    }
  }

  //获取最大值
  getMaxValue(): T | null {
    //一直往右节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }
    return current.value;
  }

  //获取最小值
  getMinValue(): T | null {
    //一直往左节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }
    return current.value;
  }

  //searchNode
  private searchNode = (root: TreeNode<T> | null, value: T): TreeNode<T> | null => {
    if (!root) return root;
    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;

    while (current) {
      if (current.value === value) {
        return current;
      } else if (current.value < value) {
        parent = current;
        current = current.right;
      } else {
        parent = current;
        current = current.left;
      }
      if (current) {
        current.parent = parent;
      }
    }
    return null;
  };

  //搜索元素
  search(value: T): boolean {
    return !!this.searchNode(this.root, value);
  }

  //寻找后驱节点
  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> | null {
    //获取右子树
    let current = delNode.right;
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) {
        current.parent = successor;
      }
    }

    if (successor !== delNode.right) {
      successor!.parent!.left = successor!.right;
      if (successor?.right) {
        successor.right.parent = successor.parent;
      }
    } else {
      delNode.right = successor!.right;
      if (successor?.right) {
        successor.right.parent = delNode;
      }
    }

    // //将删除的节点left，赋值给后继节点的left
    // successor!.left = delNode.left;
    return successor;
  }

  //删除元素
  remove(value: T) {
    //获取当前节点
    let currentNode = this.searchNode(this.root, value);
    //要删除的节点不在树结构中
    if (!currentNode) return false;

    let delNode: TreeNode<T> = currentNode;

    let replaceNode: TreeNode<T> | null = null;

    if (!currentNode.left && !currentNode.right) {
      replaceNode = null;
    } else if (currentNode.right === null) {
      replaceNode = currentNode.left;
    } else if (currentNode.left === null) {
      replaceNode = currentNode.right;
    } else {
      //找到前驱节点或者后继节点，去替换要删除的节点
      const successorNode = this.getSuccessor(currentNode);
      // replaceNode = successorNode;
      currentNode.value = successorNode!.value;
      delNode = successorNode!;
      this.checkBalancedNode(delNode);
      return true;
    }

    if (currentNode === this.root) {
      this.root = replaceNode;
    } else if (currentNode.isLeft) {
      currentNode.parent!.left = replaceNode;
    } else {
      currentNode.parent!.right = replaceNode;
    }

    if (replaceNode && currentNode.parent) {
      replaceNode.parent = currentNode.parent;
    }
    //删除完成后，检查树是否平衡
    this.checkBalancedNode(delNode);
    return true;
  }
}
